1. Field of the Invention
The present invention relates to computer-aided design (CAD) tools for arranging the layout of features ("floorplanning") within very large scale integrated (VLSI) circuits, and in particular to timing analysis of VLSI circuit floorplans.
2. Description of the Relevant Art
Designing a very large scale integrated (VLSI) circuit, or chip, is an extremely complex task comprising numerous constituent complex tasks. One of the constituent complex tasks involved in designing a VLSI circuit is the "floorplanning" of the circuit. Typically, VLSI circuits are fabricated as a wafer on a monolithic substrate, a typical substrate being silicon. The wafer is subdivided into a grid of rectangular sections referred to as die. Each die contains a copy of the VLSI circuit. After wafer fabrication, the die are cut apart and bonded to chip carriers to be incorporated onto integrated circuit boards. The VLSI circuits comprise numerous logic gates, typically grouped together in logical functional blocks, which are interconnected by wires, commonly referred to as nets. A netlist specifies the logical manner, as opposed to the physical manner, in which the logical blocks are interconnected. The notion of floorplanning relates to the physical placement of the various logic blocks, i.e., circuit elements, on the physical layout space of the silicon die.
Floorplanning, i.e., the physical placement of the logic blocks, affects a number of aspects of the design. In particular, the physical location of the logic blocks affects the power consumption, die size, routability, and timing delays of the chip. Since nets consume precious space, the less efficiently the blocks are physically placed, the larger the die size required in order to route all of the nets.
However, in many instances the die size is fixed prior to the floorplanning phase of the design. Hence, the floorplanner must choose locations for the blocks which will allow the chip to be routed within the given constraint of the die size. If the floorplanner is not sufficiently skilled or does not have sufficient tools, he or she may not even be able to route the chip. In addition, power consumption is affected by the floorplan, in particular by the fact that certain gates may have to be increased in their size in order to meet timing constraints imposed by the clock speed of the chip.
Finally, the physical location of the logic blocks affects the timing delays, or net delays, of the chip. This is because the farther a signal must travel from one block to another, the greater the net delay.
As previously mentioned, digital logic circuits are typically comprised of functional blocks interconnected by nets. Examples of functional blocks are arithmetic logic units (ALU), data and instruction caches, register files, instruction microcode blocks, etc. These blocks are comprised of more elementary logic circuits such as flip-flops, AND gates, OR gates, EXCLUSIVE OR gates, inverters, etc. These logic elements in turn comprise transistors. Transistors, or other semiconductor devices, such as capacitors, resistors, diodes, etc., comprise terminals as shown in FIG. 1. In FIG. 1, the transistor comprises a source terminal, a drain terminal and a gate terminal.
Higher level logic blocks also include terminals, which are the terminals of the logic elements of the logic block at the interface of the logic block. For example, an ALU may have a carry bit terminal, wherein the carry bit terminal is actually an output terminal of an AND gate which is part of the carry bit circuitry of the ALU, and the output terminal of the AND gate is the terminal of a transistor which is part of the AND gate. Thus, a hierarchical structure exists among the various circuit elements.
The wires which connect the terminals are referred to as nets. A net is comprised of one or more signal paths. The portion of a net which connects a source terminal and a destination terminal on a net is a path. If a net has only two terminals, then the net has only one path, i.e., the connection between the two terminals.
The combinatorial and sequential logic elements of an integrated circuit are governed by a clock signal, which clocks digital values into logic elements such as flip-flops according to a clock cycle. Signals are generated by source logic blocks or elements. These signals incur propagation delays through the transistors of the logic block, and reach a valid logic level at a source (or driver) terminal of the logic block at some time later relative to a rising or falling edge of the clock signal. The amount of time from the beginning of the clock cycle to the time when the source terminal drives the signal to a valid logic level is commonly referred to as the "driven at" (DA) time.
Likewise, signals must be received by destination (or load, or receiver) terminals of destination logic blocks or elements. The signals must arrive at the destination terminals a certain amount of time prior to the next clock cycle to allow for propagation delay time through the transistors of the destination block. The amount of time prior to the next clock cycle which the destination terminal requires the signal level to be valid is commonly referred to as the "needed by" (NB) time. The DA and NB times are referred to as timing constraints.
When logic designers design logic blocks, they specify the timing constraints of the various terminals of the blocks as part of the design information of the chip. A floorplan design must take the timing constraints into consideration and meet the timing constraints set forth in order for the chip to reliably operate at the desired clock rate. Designers commonly employ the notion of "slack time" to evaluate whether or not the timing constraints are being satisfied.
Referring now to FIG. 2, two timing diagrams illustrating slack time calculations are shown. In FIG. 2, a single clock cycle is shown in which a clock cycle begins on the rising edge of the clock signal. The slack time is calculated according to the following equation: EQU slack time=clock cycle value-(DA+NB+net delay)
The clock cycle value is the amount of time which passes during one clock cycle of the circuit being designed. The net delay is the amount of time required for the signal to be transmitted from the source terminal to the destination terminal. FIG. 2 shows a slack calculation for one path in which the slack time is positive. The path is a "passing" path in that it meets the specified timing constraints. FIG. 2 also shows a slack calculation for a second path in which the slack time is negative. The path is a "failing" path in that it does not meet the specified timing constraints.
The net delay is a function of several properties. In particular, the path length and fanout (number of loads on the net associated with the path), inter alia, determine the net delay. The path length affects the net delay in that a finite of amount of time (nanoseconds or picoseconds) is required for the signals to travel a given amount of distance (microns) on a given net.
Historically, the propagation delay of a signal through a logic gate dominated the net delay of the signal from the source gate to the destination gate. That is, the time required for the signal to be generated through the source gate and received through the destination gate was relatively much greater than the net delay of the signal along the path between the source and destination gates. However, as the geometries of VLSI circuits continues to decrease, the propagation delays through logic gates also continues to decrease. Coincidentally, the die sizes of VLSI circuits have tended to increase. Thus, with modern submicron circuit technologies, net delays have come to be equal to, or in some cases surpass, gate propagation delay times.
As a result, floorplanning is taking a more prominent role in the design of VLSI circuits. The problem of floorplanning a VLSI chip is classified as a complex design task (Sriram, D. Knowledge-Based Approaches to Structural Design, CM Publications, 1987) which requires experience, innovation and creativity and which is among the most "difficult" of real-world design problems. The problem is complex because it requires the floorplan designer to make decisions based on a vast multi-dimensional array of factors, many of which require intuitive generalizations based on experience.
The amount of information a floorplan designer must analyze has increased dramatically and the problem has become more complicated by the addition of complex, multi-dimensional timing constraints which are not easily expressed in the two-dimensional and three-dimensional geometric paradigm within which floorplan designers are accustomed to working.
A paper "LEFT--A System that Learns Rules about VLSI-design from Structural Descriptions" (by Jurgen Hermann and Renate Beckmann from the Unversity of Dortmund, Germany, published in the journal, "Applied Artificial Intelligence, An International Journal", Vol. 8, No. 1, 1994) pointed out that the quality of a floorplan solution is difficult to measure and that only "intuitive, interactive" or "artificial learning rule-based" techniques would be able to yield good results. The authors of the paper prototyped a learning-based floorplanner which "learns" complex rules by "watching" an experienced floorplanner do his work.
Other related work includes an interactive timing driven floorplanner described in an article by G. Vijayan, et. al., "Pepper--a Timing Driven Early Floorplanner" ICCD 1995 (Oct. 2-4, 1995) (herein incorporated by reference), which describes a floorplanning tool developed at IBM. The Pepper tool helps users edit a floorplan based on timing constraints and interactive inputs. The Pepper tool attempts to quantify "timing quality" using a cost function which assigns a one-dimensional scalar value to the "quality" of a floorplan design. That is, the Pepper tool provides a single number which is a relative indication of the "goodness" or "badness" of a particular floorplan, but does not, in general, provide feedback regarding specific elements of the design which contribute to its goodness or badness, such as feedback related to the timing constraints from which the numerical grade was determined.
This single scalar numeric grade is more suited to use by an automated design tool for automatically searching the entire solution space for an optimal solution for a given cost function. However, the single number cost function feedback provided by the Pepper tool is not as useful to an intelligent, experienced floorplan designer, who is capable of using much more complex multi-dimensional feedback to improve a design. An automatic tool such as the Pepper tool does not take into account "difficult to express" constraints which the human floorplan designer may have determined from experience. Thus, an improved method of providing feedback regarding the "timing quality" of a particular floorplan alternative in a way that can be used by an experienced floorplan designer is desirable.